Quantum algorithms are global random searching algorithms based on the principles, laws and effects of quantum mechanics. They are used for controlling a process or for processing data in a database, and more specifically, for controlling a process that may include search-of-minima intelligent operations.
In the quantum search, each design variable is represented by a finite linear superposition of initial states, with a sequence of elementary unitary steps manipulating the initial quantum state |i (for the input) such that a measurement of the final state of the system yields the correct output. Usually, three principle operators, i.e., linear superposition (coherent states), entanglement and interference are used in the quantum search algorithm.
A general description of quantum algorithms is contained in U.S. patent application Ser. No. 10/615,446 and in the European patent application no. 02425672.9. Both of these applications are assigned to the current assignee of the present invention.
For a better understanding, a detailed description of the Grover's quantum algorithm is presented below. Grover's problem may be stated as follows:
InputA function f:{0,1}n →{0,1} suchthat∃x∈{0,1}n:(f(x)=1 ∀y∈{0,1}n:x≠y (y)=0)ProblemFind x
In a Deutsch-Jozsa's algorithm there are two classes of input functions and it must be determined what class the input function belongs to. In this case the problem is in some sense identical in its form, even if it is more difficult because now we are dealing with 2n classes of input functions (each function of the kind described forms a class).
The diagram of the Grover's algorithm is depicted in FIG. 1, and the gate equation isΦ=[(DnI)·UF]h·(n+1H)  (1)Operator Dn is called a diffusion matrix of order n and is responsible for interference in this algorithm. The diffusion matrix is defined as follows:
Dn|0 . . . 0>|0 . . . 1>. . .|i>. . .|1 . . . 0>|1 . . . 1>|0 . . . 0>−1 + 1/2n−11/2n−1. . .1/2n−1. . .1/2n−11/2n−1|0 . . . 1>1/2n−1−1 + 1/2n−1. . .1/2n−1. . .1/2n−11/2n−1........................|i>1/2n−11/2n−1. . .−1 + 1/2n−1. . .1/2n−11/2n−1........................|1 . . . 0>1/2n−11/2n−1. . .1/2n−1. . .−1 + 1/2n−11/2n−1|1 . . . 1>1/2n−11/2n−1. . .1/2n−1. . .1/2n−1−1 + 1/2n−1
Grover's algorithm may be implemented in routines for searching a desired item in a set, by representing in vector form each item of the set forming an input set of vectors, and applying a Grover's algorithm to this set of vectors. The output vector represents the desired item.
The implementation of the Grover's algorithm clearly implies the calculation of several vector products. In fact, all qubits must be multiplied by the Hadamard matrix H, then by the entanglement matrix UF, and all qubits but the latter must be multiplied by matrix Dn.
These multiplications could be carried out via software, but it is quite evident that the number of qubits of a quantum algorithm is very critical in terms of computational speed. In fact, referring to the scheme in FIG. 1, it must be noted that the addition of only one qubit doubles the dimensions of matrices. Thus, the number of elements (and products) increases exponentially.
A method of performing the superposition operation of a Grover's or Deutsch-Jozsa's quantum algorithm over an input set of vectors is disclosed in the European patent application no. 01830383.4, which is assigned to the current assignee of the present invention. This method exploits the fact that any rotated vector obtained performing the Hadamard rotation H (on an input vector) contemplated by the superposition operation of these quantum algorithms can be easily encoded in a binary vector. Therefore, the successive tensor product of the rotated vectors for generating linear superposition vectors can be carried out by logic gates. This fact allows a noticeable time saving because logic gates are very fast.
However, this is not sufficient to significantly speed up running these quantum algorithms because the entanglement matrix UF is a 2n+1×2n+1 square matrix, which implies a considerable computational weight both in the Grover's algorithm as well as in the Deutsch-Jozsa's algorithm.
Differently from other quantum algorithms, in the Grover's algorithm it is possible to iterate h times the entanglement and interference operations until the best solution is reached. An example of evolution of the Grover's algorithm with n=3 is given in FIG. 2a, in which basis vector (Step 0) and superposition (Step 1), entanglement (Step 2) and interference (Step 3) output vectors are reported in order. Iterating the entanglement and interference operations produces a better distribution of probability amplitudes.
Each value is a component on the output vector referred to a basis of vectors of n+1 qubits. There are couples or pairs of values of opposite sign, referred to vectors of the basis having in common the first (leftmost) n qubits. For example, the values 0.625 and −0.625 are referred to vectors |0110 and |0111, respectively. Each pair of elements having an opposite sign represents the probability amplitude of a certain element of the database. For the considered example, the value 0.625 is the probability of the element associated to vector |011 after 3 iterations (h=3).
The algorithm may be iterated as far as a certain quantity is to be minimized, calculated as a function of the components of the output vector, and is smaller than a certain pre-established value. For instance, this quantity can be the Shannon entropy:
                              S          ⁡                      (            h            )                          =                  -                                    ∑                              k                =                1                                            2                                  n                  +                  1                                                      ⁢                                                                                                                        q                      k                                        ⁡                                          (                      h                      )                                                                                        2                            ⁢                                                          ⁢              log              ⁢                                                                                                            q                      k                                        ⁡                                          (                      h                      )                                                                                        2                                                                        (        2        )            where qk(h) is the k-th component of the output vector Q taken after h iterations.
The components of the output vector obtained after h=15 iterations are represented in FIG. 2b. From FIG. 2b it is clear that the element of the database to be found is associated to vector |011, and after 15 iterations the Grover's quantum algorithm will find it with a probability of about 0.69.
From the above discussion it is evident that the large number of computations for the Grover's algorithm represents a considerable burden because multiplications by the entanglement matrix UF and the interference matrix DnI might be repeated many (h) times to produce the best result, and the process may take considerable time.